/*
 * @lc app=leetcode.cn id=28 lang=java
 *
 * [28] 实现 strStr()
 */

// @lc code=start
class Solution {
    public int strStr(String haystack, String needle) {
        // return haystack.indexOf(needle);
        //前缀表不减一KMP算法
        if(needle.length()==0) return 0;
        int[] next=new int[needle.length()];
        getNext(next, needle);//获得前缀表

        int j=0;//模式串下标
        for(int i=0;i<haystack.length();i++){
            while(j>0&&needle.charAt(j)!=haystack.charAt(i)){
                j=next[j-1];
            }//不匹配时回退操作
            if(needle.charAt(j)==haystack.charAt(i)){
                j++;
            }
            if(j==needle.length()){
                return i-needle.length()+1;
            }
        }
        return -1;
    }

    private void getNext(int[] next,String s){
        //j指向前缀末尾
        int j=0;
        next[0]=0;
        for(int i=1;i<s.length();i++){//i指向后缀末尾
            //前后缀不相等，j要不断回退
            while(j>0&&s.charAt(j)!=s.charAt(i)){
                j=next[j-1];
            }
            //前后缀相等，j继续前进，并更新next
            if(s.charAt(j)==s.charAt(i)){
                j++;
            }
            next[i]=j;

        }

    }
}
// @lc code=end

